package problem.nc015;

import java.util.*;


public class Solution {

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();

    /**
     *  二叉树的层序遍历
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList <>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0;i<size;i++){
                TreeNode poll = queue.poll();

                if(poll.left != null){
                    queue.offer(poll.left);
                }

                if(poll.right != null){
                    queue.offer(poll.right);
                }

                list.add(poll.val);
            }
            ret.add(list);
        }
        return ret;
    }
}
